1. Field of Invention
The present invention relates generally to mass digital data storage systems. More particularly, the present invention relates to systems and methods for enabling pages of a block to effectively be written to substantially out of sequence.
2. Description of the Related Art
The use of non-volatile memory systems such as flash memory storage systems is increasing due to the compact physical size of such memory systems, and the ability for non-volatile memory to be repetitively reprogrammed. The compact physical size of flash memory storage systems facilitates the use of such storage systems in devices which are becoming increasingly prevalent. Devices which use flash memory storage systems include, but are not limited to, digital cameras, digital camcorders, digital music players, handheld personal computers, and global positioning devices. The ability to repetitively reprogram non-volatile memory included in flash memory storage systems enables flash memory storage systems to be used and reused.
In general, flash memory storage systems may include flash memory cards and flash memory chip sets. Flash memory chip sets generally include flash memory components and a controller components. Typically, a flash memory chip set may be arranged to be assembled into an embedded system. The manufacturers of such assemblies or host systems typically acquire flash memory in component-form, as well as other components, then assemble the flash memory and the other components into a host system.
The ability to efficiently use flash memory is crucial in enabling an overall flash memory system to meet high performance standards. In general, an inefficient use of flash memory may result in frequent erase operations and frequent write operations which may slow the operation of the overall flash memory system considerably. For example, as shown in FIG. 1, a physical block 100 may include contents 104 associated with a third page and an a third to last page of a logical block (not shown). When an update 110 associated with the logical block (not shown) is received that is associated with a fourth page of the logical block, although space is available within physical block 100, update 110 may not be stored into physical block 100, since a page ‘N-2’ 112a has already been written to, and update 110 would be intended for a page ‘3’ 112b. That is, when later pages of physical block 100 such as page ‘N-2’ 112a have been written to, previous pages of physical block 100 such as page ‘3’ 112b may not be written to.
Allowing update 110 to be written into physical block 100 would generally result in an out-of-sequence violation, e.g., a write violation. In some flash memory systems which include NAND flash memory such as MLC NAND flash memory, out-of-sequence writes and partial writes are not allowed. Hence, it is often not possible to write update 110 into page ‘3’ 112b once contents 104b are present in page ‘N-2’ 112a. 
In order to accommodate update 110, a new physical block 120 is typically obtained. Then, contents 104a, update 110, and contents 104b are written into new physical block 120. Once new physical block 120 is written into, then contents of physical block 100 may be erased. When updates associated with a fourth page of the logical block (not shown) are constantly made, repeated processes of obtaining a new physical block, writing to the new physical block, and erasing old physical blocks may be necessary. As a result, substantially only three pages of each physical block which contains ‘N’ pages may be written, while a number of pages, i.e., N-3 pages, remain substantially empty. Effectively wasting N-3 pages in each physical block, while generally requiring a relatively high number of write and erase processes, may cause an overall flash memory system to operate inefficiently. Enabling pages of a physical block such as physical block 100 to be written such that memory resources may be used more efficiently may allow the performance of an overall flash memory system such as an MLC NAND flash memory system to be improved.
Therefore, what is needed is a system and a method which allows memory resources in a non-volatile memory system to be used more efficiently. Specifically, what is desired is a system and a method which may effectively allow physical pages of a physical block in a memory system such as an MLC NAND flash memory system to be written substantially out-of-sequence.